\documentclass[fleqn,10pt]{article}
\usepackage{graphicx} % Required for inserting images
\usepackage{xeCJK} 
\usepackage{amsmath}
\usepackage{pgfplots}
\usepackage{subcaption}
\usepackage{listings}
\usepackage{mdframed}
\usepackage[dvipsnames]{xcolor}

\title{Homework03  Report  of  D.S.A.\\{硬币找零问题}}
\author{3220101611  韩耀霆}
\date{\today}

\begin{document}
\flushbottom
\maketitle
\tableofcontents

\section{题目要求}
你有一定初始硬币数目的几种不同的美元硬币:1,5,10,25美分.输入每种硬币的数量,目标是找出使得总金额为n美分(也是输入)的最小硬币数.

\section{题目解答}
\subsection{算法选择}
由于硬币数量是给定的，使用贪心算法虽然很巧妙，但可能会出现一些比较麻烦的考虑，为了使得代码更加稳定且易于维护和修改，故我们由题中所给提示利用动态规划实现算法.具体的实现参考https://zhuanlan.zhihu.com/p/615326043

\subsection{代码思路}
如果上来我们直接解决提中所给的问题显然有一定的难度，故我们不妨先假设我们有各种面值的硬币无限多个.
\subsubsection{无限数量硬币的情况}
我们有1,5,10,25四种面值的硬币,定义一个数组int Min[i]为金额i对应的最小硬币数，取Min[0]=0，令Min[i](i $\neq$ 0)=INT \_ MAX，不妨考虑其递推如下：
\begin{itemize}
    \item 只用面值为1的硬币：\\
        得到Min[i]=min(Min[i],Min[i-1]+1);
    \item 在使用面值为1的硬币的基础上增加面值为5的硬币：\\
        对上面处理过后的数组得到Min[i]-min(Min[i],min[i-5]+1);
    \item 在以上内容的基础上我们再考虑加入面值为10和25面值的硬币：\\
        更多地我们可以有Min[i]=min(Min[i],Min[i-10]+1)和Min[i]=min(Min[i],Min[i-25]+1);\\
我们利用简单的循环来处理（这里我们仅使用伪代码来表明核心内容，后续未注明是代码的部分同）：
\begin{lstlisting}[language=C++, numbers=left, numbersep=2em, basicstyle=\ttfamily, breaklines=true]
int money_Amount = m;                //总金额
int type_Num = n;                    //硬币种类数
int type[VALUE] = {1, 5, 10, 25, 50};//硬币面值
int Min[MONEY];                      //所求最小硬币数

for (int j = 0; j < VALUE; j++)      //从第一种硬币开始往后递推
    for (int i = type[j]; i < MONEY; i++)
        Min[i] = min(Min[i], Min[i - type[j]] + 1); // 递推式

\end{lstlisting}
\end{itemize}
接下来我们考虑题设中的要求，也即每种硬币的数量是所给定的.
\subsubsection{有限数量硬币的情况}
我们对硬币赋两个属性：
\begin{lstlisting}[language=C++, numbers=left, numbersep=2em, basicstyle=\ttfamily, breaklines=true]
struct COIN{
    int Value;       //硬币面值
    int Count;       //硬币现有数量
}
\end{lstlisting}
之后对无限数量硬币情况做一定的修改，引入新的限制条件，由此得到：
\begin{lstlisting}[language=C++, numbers=left, numbersep=2em, basicstyle=\ttfamily, breaklines=true]
for (int i = 1; i <= Charges; i++) {    //类似于递推式
    for (COIN coin : coins){    //遍历所有币种
        for (int j = 0; j < coin.Count; j++) {  //在数量限制下遍历该种硬币递推式
            if (coin.Value <= i) {
                int Sub_res = dp[i - coin.Value];
                if (Sub_res != INT_MAX && Sub_res + 1 < dp[i] && coin.Count > 0) {//择优取用
                    dp[i] = Sub_res + 1;
                    coin.Count--;
                    }
                }
            }
        }
    }
\end{lstlisting}
\subsubsection{思路总结}
整体的思路构建不存在任何问题，在这种算法中，取$k$为硬币种类，$n$为目标金额，$m_i$(其中$i \in [1,k] \cap Z$)为硬币个数，其平均时间复杂度约为$O(kn\bar{m})$，针对题中问题，平均时间复杂度约为$O(n\bar{m})$.

\subsection{完整代码}
此处只展示包含算法的coin.h，注释等请见原码.
\begin{lstlisting}[language=C++, numbers=left, numbersep=2em, basicstyle=\ttfamily, breaklines=true]
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;  

struct COIN {  
    int Value;          
    int Count;
};  

int Min_coins (int Charges, vector<COIN>& coins) {
    vector<int> dp(Charges + 1, INT_MAX);
    dp[0] = 0;          
    
    for (int i = 1; i <= Charges; i++) {
        for (COIN coin : coins){
            for (int j = 0; j < coin.Count; j++) {
                if (coin.Value <= i) {
                    int Sub_res = dp[i - coin.Value];
                    if (Sub_res != INT_MAX && Sub_res + 1 < dp[i] && coin.Count > 0) {
                        dp[i] = Sub_res + 1;
                        coin.Count--;
                    }
                }
            }
        }
    }

    return dp[Charges] == INT_MAX ? -1 : dp[Charges];
}
\end{lstlisting}

\section{测试用例分析}
测试用例输入为input.txt，执行程序为main.cpp其中主要针对以下几个部分做出了验证：
\subsubsection{题设要求的完成情况}
\begin{itemize}
    \item 正常的实际有解使用事例；
    \item 用以数量有限与无限的区分的事例；
    \item 无解的实际事例；
    \item 极度恶劣情况的事例.
\end{itemize}

\subsubsection{算法时间复杂度的验证}
这一部分实际已经加入了main.cpp，比较可以看出确实符合基本的预期.

\end{document}
